package com.ryujung.greedy;

import java.util.Arrays;

class Solution1005 {

    /**
     * 思路：
     * 有负数，反转最小的负数，
     * 没有负数，反转最小的正数，
     * <p>
     * 如何首先反转最小的负数？
     * 将数组进行排序
     * 如何反转最小的正数？
     * <p>
     * 需要将负数反转后的数组再次排序，在根据k是否>0分情况处理：
     * 如果k大于0，说明已经没有负数了，如果k为奇数，则反转最小的非负数（可能是0）
     * 如果是偶数，则
     * <p>
     * 解答成功:
     * 执行耗时:2 ms,击败了98.17% 的Java用户
     * 内存消耗:41.1 MB,击败了45.61% 的Java用户
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                nums[i] = k-- > 0 ? -nums[i] : nums[i];
            } else {
                break;
            }
        }
        Arrays.sort(nums);
        if (k > 0 && k % 2 != 0) {
            nums[0] = -nums[0];
        }
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

    /**
     * [4,2,3]
     * 1
     */
    public static void main(String[] args) {
        Solution1005 s = new Solution1005();
        // 5
        System.out.println(s.largestSumAfterKNegations(new int[]{4, 2, 3}, 1));
        // 32
        System.out.println(s.largestSumAfterKNegations(new int[]{-2, 9, 9, 8, 4}, 5));
    }
}